COMMENT ⊗   VALID 00011 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	{M2BDJ25.FNT[XGP,SYS]FAFDFA}
C00005 00003	{λ40JAFA}TITLE PAGE.{JR} AUGUST  1974.
C00007 00004	{λ40JCFD} COPYRIGHT NOTICE.
C00008 00005	{λ40JCFD} SIGNATURE PAGE FOR Ph.D. DISSERTATION.
C00010 00006	{λ40JCFD} CONTENTS.
C00011 00007	{JVλ5JCFD} DETAILED TABLE OF CONTENTS.
C00013 00008	{JVλ5JCFD} DETAILED TABLE OF CONTENTS.
C00014 00009	{JCFD} LIST OF BOXES.
C00016 00010	{JCFD} LIST OF FIGURES.
C00018 00011	{JCFD} ACKNOWLEDGEMENTS.
C00026 ENDMK
C⊗;
{M2BDJ25.FNT[XGP,SYS];FA;FD;FA}
{JA;FA}COVER PAGE.{JR} AUGUST  1974.
{JU}\draft - draft - draft - draft - draft - draft - draft - draft - draft - draft - draft - draft - draft - draft
{H4;JA;I∂0,0;V∂0,1260;}


{I400,0;JC;FD}          GEOMETRIC  MODELING  FOR  COMPUTER  VISION.

{I600,0;JC;FD}                   BRUCE  G.  BAUMGART

{I800,0;λ17;JU;FA}ABSTRACT:

	The main idea of this thesis is that a 3-D geometric model of
the physical  world is an essential part  of a general purpose vision
system.  Such a model provides a goal for descriptive image analysis,
an origin for image synthesis (for  verification),  and a context for
spatial  problem solving.  Some  of the design  ideas to be presented
have been  implemented  in two  programs named  GEOMED  and CRE;  the
programs  are  demonstrated  in  situations involving  camera  motion
relative to a static world.

{λ5;H4;I1600,0;V1600,1260;I1600,0;JU;F2}
	This research was supported in part  by the Advanced Research
Projects  Agency of  the  Office of  the Secretary  of  Defense under
Contract No. SD-183.
The views  and  conclusions contained  in this  document  are
those  of the  author and  should not  be interpreted  as necessarily
representing  the official policies, either  expressed or implied, of
the Advanced Research Project Agency or the United States Government.
{H4;I∂0,0;V∂0,1260;}
{λ40;JA;FA}TITLE PAGE.{JR} AUGUST  1974.
{I400,0;JC;FD} GEOMETRIC  MODELING  FOR  COMPUTER  VISION.

{JCFA}                     A DISSERTATION
{JC}       SUBMITTED TO THE DEPARTMENT OF COMPUTER SCIENCE
{JC}            AND THE COMMITTEE ON GRADUATE STUDIES
{JC}                   OF STANFORD UNIVERSITY
{JC}         IN PARTIAL FULFILLMENT OF THE REQUIREMENTS
{JC}                      FOR THE DEGREE OF
{JC}                    DOCTOR OF PHILOSOPHY

{JC}                             BY
{JC}                      BRUCE  G.  BAUMGART
{JC}                         AUGUST  1974
{H4;I310,0;V310,1260;
I460,0;V460,1260;
I1020,0;V1020,1260;
I1260,0;V1260,1260;
I1900,0;JC;FA} - i -
{λ40;JCFD} COPYRIGHT NOTICE.

{I800,500;H4;C50;C30,π/4,3*π/2;}

{I800,0;JC} COPYRIGHT 1974.

{I950,0;JC} BY

{I1100,0;JC} BRUCE GUENTHER BAUMGART

{I1900,0;JC;FA} - ii -
{λ40;JCFD} SIGNATURE PAGE FOR Ph.D. DISSERTATION.

{JU;FA}
\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.

Principle Adviser

\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.

\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.

\I certify that I have read this thesis and that in my
opinion it is fully adequate, in scope and quality, as a dissertation
for the degree of Doctor of Philosophy.

Approved for the University Committee on Graduate Studies:

Dean of Graduate Studies.

{JA;I1900,0;JC;FA} - iii -
{λ40;JCFD} CONTENTS.
{JAFA}

(INTRO)		0.	INTRODUCTION.
(GEM)			1.	GEOMETRIC MODELING THEORY.
(WINGED)		2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.
(GEOMED)		3.	A GEOMETRIC MODELING SYSTEM.
(OCCULT)		4.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.
(BIN)			5.	A POLYHEDRON INTERSECTION ALGORITHM.
(VIS)			6.	COMPUTER VISION THEORY.
(CNTOUR)		7.	VIDEO IMAGE CONTOURING.
(CMPARE)		8.	IMAGE COMPARING.
(CAMERA)		9.	CAMERA AND FEATURE LOCUS SOLVING.
(CONCLU)		10.	RESULTS AND CONCLUSIONS.

APPENDICES:

(REF)				REFERENCES.
(GNODES)			GEOMED NODE FORMATS.
(CNODES)			CRE NODE FORMATS.
{I1900,0;JC} - iv -
{JV;λ5;JCFD} DETAILED TABLE OF CONTENTS.
{FA}
SECTION  0.	INTRODUCTION.

SECTION  1.	GEOMETRIC MODELING THEORY.

		1.0	Introduction to Geometric Modeling.
		1.1	Kinds of Geometric Models.
		1.2	Polyhedron Definitions and Properties.
		1.3	Camera, Light and Image Modeling.
		1.4	Related Modeling Work.

SECTION  2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.

		2.0	Introduction to the Winged Edge.
		2.1	Winged Edge Link Fields.
		2.2	Perimeter Accessing.
		2.3	Edge and Face Splitting.
		2.4	Basic Polyhedron Synthesis.
		2.5	Coordinate Free Polyhedron Representation.

SECTION  3.	A GEOMETRIC MODELING SYSTEM.

		3.0	Introduction to GEOMED.
		3.1	Euler Routines.
		3.2	Euclidean Routines.
		3.3	Image Synthesis Routines.

SECTION  4.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.

		4.0	Introduction to hidden line elimination.
		4.1	Hiding a Topologically Coherent Object.
		4.2	Two hidden line eliminators that almost work.
		4.3	2-D Partition Sort of Faces, Edges and Vertices.
		4.4	Propagating Underfaces.
		4.5	Shadows.
		4.6	Photometric Modeling and Video Generation.
		4.7	Performance.

SECTION  5.	A POLYHEDRON INTERSECTION ALGORITHM.


{I1900,0;JC} - v -
{JV;λ5;JCFD} DETAILED TABLE OF CONTENTS.
{JCFA} (continued).

SECTION  6.	COMPUTER VISION THEORY.
	
	6.0	Introduction to Computer Vision Theory.
	6.1	A Geometric Feedback Vision System.
	6.2	Vision Tasks.
	6.3	Vision System Design Arguments.
	6.4	Mobile Robot Vision.
	6.5	Related Vision Work.
	6.6	Summary.

SECTION  7.	VIDEO IMAGE CONTOURING.

SECTION  8.	IMAGE COMPARING.

SECTION  9.	CAMERA AND FEATURE LOCUS SOLVING.

SECTION 10.	RESULTS AND CONCLUSIONS.
{I1900,0;JC;FA} - vi -
{JC;FD} LIST OF BOXES.
{JAFA}
SECTION  0.	INTRODUCTION.

SECTION  1.	GEOMETRIC MODELING THEORY.

		1.1	Ten Kinds of Geometric Models.
		1.2	Desirable Properties for a Geometric Model.
		1.3	Properties of Polyhedra.

SECTION  2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.

SECTION  3.	A GEOMETRIC MODELING SYSTEM.

SECTION  4.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.

SECTION  5.	A POLYHEDRON INTERSECTION ALGORITHM.

SECTION  6.	COMPUTER VISION THEORY.

SECTION  7.	VIDEO IMAGE CONTOURING.

SECTION  8.	IMAGE COMPARING.

SECTION  9.	CAMERA AND FEATURE LOCUS SOLVING.

SECTION 10.	RESULTS AND CONCLUSIONS.
{I1900,0;JC;FA} - vii -
{JCFD} LIST OF FIGURES.
{JAFA}
SECTION  0.	INTRODUCTION.
	 0.1	Horse Shaped Polyhedra Derived from Video Images.
	 0.2	Model of Water Pump.
	 0.3	Example of Predicted Video and Perceived Video.
	 0.4	Example of Predicted and Perceived Contour Images.

SECTION  1.	GEOMETRIC MODELING THEORY.

SECTION  2.	THE WINGED EDGE POLYHEDRON REPRESENTATION.
	 2.1	Winged Edge Topology.
	 2.2	Three Kinds of Perimeters: Face, Edge and Vertex.
	 2.3	ESPLIT and KLEV.
	 2.4	MKFE and KLFE.
	 
SECTION  3.	A GEOMETRIC MODELING SYSTEM.

SECTION  4.	HIDDEN LINE ELIMINATION FOR COMPUTER VISION.

SECTION  5.	A POLYHEDRON INTERSECTION ALGORITHM.

SECTION  6.	COMPUTER VISION THEORY.

SECTION  7.	VIDEO IMAGE CONTOURING.

SECTION  8.	IMAGE COMPARING.

SECTION  9.	CAMERA AND FEATURE LOCUS SOLVING.

SECTION 10.	RESULTS AND CONCLUSIONS.
{I1900,0;JC;FA} - viii -
{JCFD} ACKNOWLEDGEMENTS.
{FA}
The following people personally contributed to this work:

Thesis Adviser:	John Mc Carthy
Readers:		Jerome A. Feldman
			Donald E. Knuth
			Alan C. Kay

Jerry Agin, Leona  Baumgart, Tom  Binford,  Jack  Buchanan, Les  Earnest,
Tom  Gafford, Steve  Gibson, Ralph  Gorin, Tovar  Mock, Andy  Moorer,
Hans  Moravec, Richard Orban, Ted  Panofsky, Lou  Paul, Lynn  Quam,
Jeff  Raskin, Ron  Rivest, Irwin Sobel, Robert  Sproull,
Dan  Swinehart, Russel  Taylor, Marty Tenenbaum, Arthur  Thomas.

{I1900,0;JC;FA} - ix -